package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;

/**
 * @author: ZhouBert
 * @date: 2021/4/2
 * @description: 面试题 17.21. 直方图的水量
 * https://leetcode-cn.com/problems/volume-of-histogram-lcci/
 */
public class C_面试题17_21_直方图的水量 {
	static C_面试题17_21_直方图的水量 action = new C_面试题17_21_直方图的水量();

	public static void main(String[] args) {
		test1();
		test2();
		test3();
	}


	public static void test1() {
		//6
		int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
		int res = action.trap(height);
		System.out.println("res = " + res);
	}

	public static void test2() {
		//1
		int[] height = new int[]{4, 2, 3};
		int res = action.trap(height);
		System.out.println("res = " + res);
	}

	public static void test3() {
		//
		int[] height = new int[]{0, 7, 1, 4, 6};
		int res = action.trap(height);
		System.out.println("res = " + res);
	}

	/**
	 * 可以将 arr 进行优化，每一次计算高度和宽度相乘即可，摆脱遍历。
	 *
	 * @param height
	 * @return
	 */
	public int trap(int[] height) {
		int len = height.length;
		//保留索引
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		//记录每个孔水高
		int[] arr = new int[len];
		//init 找到第一个入栈的位置
		int i = 0;
		for (; i < len; i++) {
			if (height[i] != 0) {
				stack.addLast(i);
				break;
			}
			arr[i] = 0;
		}
		i++;
		if (i == len) {
			//如果都是 0
			return 0;
		}
		int tempMax = 0, beginIndex = 0, end = 0;
		//开始指定方案处理
		for (; i < len; i++) {
			if (height[i] <= height[stack.peekLast()]) {
				//小于直接入栈
				stack.addLast(i);
			} else {
				end = i;
				while (!stack.isEmpty() && height[i] >= height[stack.peekLast()]) {
					beginIndex = stack.removeLast();
					tempMax = height[beginIndex];
				}
				//
				if (!stack.isEmpty()) {
					tempMax = Math.max(tempMax, height[i]);
					beginIndex = stack.peekLast() + 1;
				}

				putArea(arr, height, beginIndex, end, tempMax);
				stack.addLast(i);
			}

		}
		//最后累计 arr 的值即可
		int res = 0;
		for (int j = 0; j < len; j++) {
			res += arr[j];
		}
		return res;
	}

	private void putArea(int[] arr, int[] height, int beginIndex, int end, int tempMax) {
		for (int i = beginIndex; i < end; i++) {
			arr[i] = tempMax - height[i];
		}

	}


}
